/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  let min = p.val > q.val ? q.val : p.val;
  let max = p.val > q.val ? p.val : q.val;

  let res = null;

  function dfs(root) {
    if (root == null) {
      return false;
    }

    let Lres = dfs(root.left);
    let Rres = dfs(root.right);

    if (Lres && Rres) {
      res = root;
      return true;
    }

    if (root.val == min) {
      if (Rres == true) {
        res = root;
        return true;
      } else {
        return true;
      }
    }

    if (root.val == max) {
      if (Lres == true) {
        res = root;
        return true;
      } else {
        return true;
      }
    }

    if (Lres || Rres) {
      return true;
    }

    return false;
  }

  dfs(root);
  return res;
};
